package _剑指offer;

import java.util.Arrays;

/**
 * 返回数组中出现次数超过一半的数字
 * 1、先排序，返回数组中间值必为 数组中超过一半的数
 * 2、摩尔投票法：
 *      result 存储每次的众数，votes 存储票数
 *      1）初始化，result=0，votes=0;
 *      2）遍历 nums 数组中的每一个 num
 *          检查如果 votes==0，让当前的 num 为众数 result
 *          如果 num == result，votes++, 否则 votes--
 *      3）返回 result
 * 3、哈希表：
 *
 * @author Liu Huan
 */

public class _39_数组中出现次数超过一半的数字 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println("methodOfSort(nums) = " + methodOfSort(nums));
        System.out.println("methodOfVote(nums) = " + methodOfVote(nums));
        System.out.println("methodOfHash(nums) = " + methodOfHash(nums));
    }
    
    public static int methodOfSort(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
    
    public static int methodOfVote(int[] nums) {
        int result = 0, votes = 0;
        for (int num : nums) {
            if (votes == 0) {
                result = num;
            }
            if (num == result) {
                votes++;
            } else {
                votes--;
            }
        }
        return result;
    }
    
    public static int methodOfHash(int[] nums) {
        
        return 0;
    }
}
